package Top200;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-27 15:01
 * 回溯
 */
public class restoreIpAddresses93 {
    List<String> res=new LinkedList<>();
    void backtrack(String s,int index,LinkedList<Integer> path,boolean canwith){
        if (index==s.length()){
            if (path.size()==4){
                //得到一个可能的答案
                StringBuffer sb=new StringBuffer();
                sb.append(path.getFirst());
                for (int i = 1; i < 4; i++) {
                    sb.append('.').append(path.get(i));
                }
                res.add(sb.toString());
            }
            return;
        }

        int last=Integer.parseInt(String.valueOf(s.charAt(index)));
        if (canwith){
            //可以与前一位合并
            int lastInt = path.getLast();
            int cur=last+lastInt*10;
            if (cur<=255){
                path.removeLast();
                path.add(cur);
                backtrack(s,index+1,path,true);
                path.removeLast();
                path.add(lastInt);
            }
        }
        if (last==0){
            path.addLast(last);
            backtrack(s,index+1,path,false);
            path.removeLast();
        }else {
            path.addLast(last);
            backtrack(s,index+1,path,true);
            path.removeLast();
        }
    }
    public List<String> restoreIpAddresses(String s) {
        if (s.length()<4) return res;
        backtrack(s,0,new LinkedList<>(),false);
        return res;
    }
}
